package com.zdp.leetcodeMiddle;

import java.util.Arrays;

public class 每个元音包含偶数次的最长子字符串 {
    public static void main(String[] args) {
        int [] pos = new int[1<<5];
        System.out.println(pos.length);
    }
    /*
    * 题目描述：
    * 给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：
    * 每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
    * */
    /*
    * 官方题解：用到了前缀和+状态压缩
    *  利用前缀和 可以求出各个元音字母 在区间内 出现的次数 ：[j,i] 区间 第k个元音字母 出现的次数 即为: pre[i][k]-pre[j][k]
    * pre 为 前i个字符 各个元音字母出现的次数
    * 符合条件的区间 五个元音字母 pre[i][k]-pre[j][k] 的值都是偶数
    * 所以问题就变成了 如何 确定i和j
    *  但发现：就算有了这个前缀和 ，还是要用双层循环 枚举j 和枚举i 来确定区间 ；如何优化？
    * 可以找找 j和i之间的关系， 但好像没有什么关系 pre[i]-pre[j] 为一个定值
    * 所以只能换个思路
    * */
    /*
    * 换个思路：
    * 首先，满足条件的 子字符串 元音字母出现的次数都是偶数次 ===> 这就意味着 pre[i][k]-pre[j][k] = 偶数
    * 奇数-奇数 = 偶数， 偶数-偶数=偶数 ===> 也就是说 一个符合条件的字符串，他的开头和结尾的前缀和的奇偶性应该是相同的
    * ===>前缀和数组 就可以从维护 元音字母出现的次数 变成 维护 元音字母出现的奇偶性
    * 那这样 就只需要 判断 j i 位置的状态是否一致（奇偶性） ===> 五个字母的状态都要一致
    * ====> 我们只要存储每个状态出现的最早位置（这边的状态都是记录五个字母的）
    * ===>枚举i，获得当前i的状态，判断是否有与i状态一致的j（我们存储的位置）===>如果有，就记录下长度，如果没有，就记录下该状态（位置+状态）
    * 状态如何表示？===>如果用哈希表来存储的话，key（位置索引）：value（每个字母的状态）
    * value = {a:奇偶，e:奇偶,i:奇偶,o:奇偶,u:奇偶}
    * 题目是只有五个元音字母，如果元音字母过多，这个value就会过于冗余
    * ====>对于有限的参数表状态===>状态压缩：这边是将状态压缩成一个五位的二进制数
    * 0 0 0 0 0 : a e i o u ===>每一位上的0/1 表示对应元音字母的奇偶性
    * 状态的取值范围为 : 0 0 0 0 0 ~ 1 1 1 1 1 ===> [0,31]
    * 奇偶性可以使用异或来运算
    *
    * */
    public int findTheLongestSubstring(String s) {
        //状态对应  0 0 0 0 0 : a e i o u
        int[] pre = new int[1<<5]; //数组的下标 表示状态  数组的值，表示该状态出现的最早位置
        int status = 0;
        //状态0出现的位置应该为-1，元音字母全部不出现也是状态0==>只有状态0是符合条件的
        Arrays.fill(pre,-1);
        pre[0] = 0; //因为当字符串为空时，就是0状态
        int maxlength = 0;
        for(int i=0;i<s.length();i++){
            switch(s.charAt(i)){
                case 'a':
                    status = status ^ (1<<4);break;
                case 'e':
                    status = status ^ (1<<3);break;
                case 'i':
                    status = status ^(1<<2);break;
                case'o':
                    status = status^(1<<1);break;
                case'u':
                    status = status^1;break;
            }
            if(pre[status]>=0){
                maxlength = maxlength<(i+1-pre[status])?i+1-pre[status]:maxlength;
            }else{
                pre[status] = i+1; //记录到当前字符的下一位，计算长度的时候要注意
            }
        }
        return maxlength;
    }

}
